package com.jxb.five;

/**
 * 在排序数组中查找元素的第一个和最后一个位置
 * 示例 1：
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 示例2：
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * 示例 3：
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 * 提示：
 * 0 <= nums.length <= 105
 * nums是一个非递减数组
 *
 * 思路：分别寻找第一个元素和最后一个元素
 *      寻找第一个元素逻辑(mid==target，移动end)：
 *          1：进行二分查找，当mid>=target,end = mid - 1
 *      寻找最后一个元素座机(mid==target，移动start)：
 *          1：进行二分查找，当mid<=target,start = mid + 1
 *
 * */
public class FindFirstLastInSortedArray_34 {

    public static void main(String[] args) {

    }

    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        //需要第一个
        res[0] = findFirst(nums,target);
        //若第一个没找到，最后一个不用找了
        if (res[0] == -1) {
            return new int[]{-1,-1};
        }else {
            //找到了第一个，找最后一个
            res[1] = findLast(res[0],nums,target);
        }
        return res;
    }

    private int findLast(int res, int[] nums, int target) {
        int idx = -1;
        int start = res;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (nums[mid] <= target) {
                start = mid + 1;
            }else {
                end = mid - 1;
            }
            if (nums[mid] == target) {
                idx = mid;
            }
        }
        return idx;
    }

    private int findFirst(int[] nums, int target) {
        int idx = -1;
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = (start + end)/2;
            if (nums[mid] >= target) {
                end = mid - 1;
            }else {
                start = mid + 1;
            }
            if (nums[mid] == target) {
                idx = mid;
            }
        }
        return idx;
    }

}
